home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / programming / source / fbm12s.lha / flthin.c < prev    next >
C/C++ Source or Header  |  1994-07-18  |  5KB  |  228 lines
  1. /*****************************************************************
  2.  * flthin.c: FBM Release 1.2 18-Apr-93 Michael Mauldin
  3.  *
  4.  * Copyright (C) 1993 by Michael Mauldin.  Permission is granted
  5.  * to use this file in whole or in part for any purpose, educational,
  6.  * recreational or commercial, provided that this copyright notice
  7.  * is retained unchanged.  This software is available to all free of
  8.  * charge by anonymous FTP and in the UUNET archives.
  9.  *
  10.  * flthin.c: 
  11.  *    Thin an image using the algorithm from "Digital Image
  12.  *    Processing", page 492-3.
  13.  *
  14.  * CONTENTS
  15.  *    thin_fbm (input, output)
  16.  *    FBM *input, *output;
  17.  *
  18.  * EDITLOG
  19.  *    LastEditDate = Sun Apr 18 23:37:20 1993 - Michael Mauldin
  20.  *    LastFileName = /usr0/mlm/src/fbm/flthin.c
  21.  *
  22.  * HISTORY
  23.  * 18-Apr-93  Michael Mauldin (mlm) at Carnegie-Mellon University
  24.  *    Created from flshrp.c
  25.  *****************************************************************/
  26.  
  27. # include <stdio.h>
  28. # include <math.h>
  29. # include <ctype.h>
  30. # include "fbm.h"
  31.  
  32. /****************************************************************
  33.  * thin_fbm: thin regions
  34.  ****************************************************************/
  35.  
  36. #ifndef lint
  37. static char *fbmid =
  38. "$FBM flthin.c <1.2> 18-Apr-93  (C) 1993 by Michael Mauldin, source \
  39. code available free from MLM@CS.CMU.EDU and from UUNET archives$";
  40. #endif
  41.  
  42. thin_fbm (input, output)
  43. FBM *input, *output;
  44. { register int i, j, k;
  45.   register unsigned char *ibm, *obm, *tbm, *tail;
  46.   int rowlen, w, h, round=0, deleted=1;
  47.   FBM temp;
  48.  
  49.   if (input->hdr.physbits != 8)
  50.   { fprintf (stderr, "thin_fbm: only 8 bit inputs may be thinned\n");
  51.     return (0);
  52.   }
  53.  
  54.   if (input->hdr.planes != 1 || input->hdr.clrlen > 0)
  55.   { fprintf (stderr, "thin_fbm: only greyscale images may be thinned, use clr2gray first.\n");
  56.     return (0);
  57.   }
  58.  
  59.   /* Allocate output */
  60.   output->hdr = input->hdr;
  61.   alloc_fbm (output);
  62.  
  63.   /* Allocate temp */
  64.   temp.hdr = input->hdr;
  65.   alloc_fbm (&temp);
  66.  
  67.   /* Cache important size values */
  68.   w = input->hdr.cols;
  69.   h = input->hdr.rows;
  70.   rowlen = input->hdr.rowlen;
  71.   
  72.   /* 
  73.    * Since we dont want to change the input, and we need two arrays
  74.    * two hold the images, we copy the input to the output, first.
  75.    * We make sure each bit is set to 0 or 1.
  76.    */
  77.  
  78.   for (ibm = input->bm,
  79.         obm = output->bm,
  80.         tail = input->bm + input->hdr.plnlen;
  81.        ibm < tail; )
  82.   { *obm++ = *ibm++ ? 1 : 0; }
  83.   
  84.   /* Do each pass repeatedly until no more points are deleted */
  85.   while (deleted)
  86.   { register int p2, p3, p4, p5, p6, p7, p8, p9, n0, s0;
  87.  
  88.     round++;
  89.     deleted = 0;
  90.     
  91.     /*
  92.      * Step one, remove points south and east of regions,
  93.      * output->cm is the input, and temp.cm is the output.
  94.      */
  95.  
  96.     for (j = 1; j < h-1; j++)
  97.     { obm = &(output->bm[j*rowlen]);
  98.       tbm = &(temp.bm[j*rowlen]);
  99.       
  100.       for (i=1; i < w-1; i++)
  101.       { if (obm[i] == 0)
  102.         { tbm[i] = 0; }
  103.     
  104.     else
  105.     {
  106.       /*
  107.        *        p9 | p2 | p3
  108.        *    ----+----+----
  109.        *     p8 | p1 | p4
  110.        *    ----+----+----
  111.        *     p7 | p6 | p5
  112.        */
  113.       
  114.       p2 = obm[i-rowlen];
  115.       p4 = obm[i+1];
  116.       p6 = obm[i+rowlen];
  117.       p8 = obm[i-1];
  118.       
  119.       /* book conditions (c) and (d) */
  120.       if (p4 && p6 && (p2 || p8))
  121.       { tbm[i] = 1; continue; }
  122.  
  123.       p3 = obm[i-rowlen+1];
  124.       p5 = obm[i+rowlen+1];
  125.       p7 = obm[i+rowlen-1];
  126.       p9 = obm[i-rowlen-1];
  127.  
  128.       n0 = p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9;
  129.       
  130.       /* Check number of neighbors */
  131.       if (n0 < 2 || n0 > 6)
  132.       { tbm[i] = 1; continue; }
  133.       
  134.       /* Count number of transitions */
  135.       s0 = (((p2 == 0) && (p3 == 1)) + 
  136.             ((p3 == 0) && (p4 == 1)) + 
  137.             ((p4 == 0) && (p5 == 1)) + 
  138.             ((p5 == 0) && (p6 == 1)) + 
  139.             ((p6 == 0) && (p7 == 1)) + 
  140.             ((p7 == 0) && (p8 == 1)) + 
  141.             ((p8 == 0) && (p9 == 1)) + 
  142.             ((p9 == 0) && (p2 == 1)));
  143.       
  144.       if (s0 != 1)
  145.       { tbm[i] = 1; continue; }
  146.       
  147.       tbm[i] = 0;
  148.       deleted++;
  149.     }
  150.       }
  151.     }
  152.     
  153.     /*
  154.      * Step two, remove points north and west of regions,
  155.      * temp.cm is the input, and output->cm is the output.
  156.      */
  157.     
  158.     for (j = 1; j < h-1; j++)
  159.     { obm = &(output->bm[j*rowlen]);
  160.       tbm = &(temp.bm[j*rowlen]);
  161.       
  162.       for (i=1; i < w-1; i++)
  163.       { if (tbm[i] == 0)
  164.         { obm[i] = 0; }
  165.     
  166.     else
  167.     {
  168.       /*
  169.        *        p9 | p2 | p3
  170.        *    ----+----+----
  171.        *     p8 | p1 | p4
  172.        *    ----+----+----
  173.        *     p7 | p6 | p5
  174.        */
  175.       
  176.       p2 = tbm[i-rowlen];
  177.       p4 = tbm[i+1];
  178.       p6 = tbm[i+rowlen];
  179.       p8 = tbm[i-1];
  180.       
  181.       /* book conditions (c') and (d') */
  182.       if (p2 && p8 && (p4 || p8))
  183.       { obm[i] = 1; continue; }
  184.  
  185.       p3 = tbm[i-rowlen+1];
  186.       p5 = tbm[i+rowlen+1];
  187.       p7 = tbm[i+rowlen-1];
  188.       p9 = tbm[i-rowlen-1];
  189.  
  190.       n0 = p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9;
  191.       
  192.       /* Check number of neighbors */
  193.       if (n0 < 2 || n0 > 6)
  194.       { obm[i] = 1; continue; }
  195.       
  196.       /* Count number of transitions */
  197.       s0 = (((p2 == 0) && (p3 == 1)) + 
  198.             ((p3 == 0) && (p4 == 1)) + 
  199.             ((p4 == 0) && (p5 == 1)) + 
  200.             ((p5 == 0) && (p6 == 1)) + 
  201.             ((p6 == 0) && (p7 == 1)) + 
  202.             ((p7 == 0) && (p8 == 1)) + 
  203.             ((p8 == 0) && (p9 == 1)) + 
  204.             ((p9 == 0) && (p2 == 1)));
  205.       
  206.       if (s0 != 1)
  207.       { obm[i] = 1; continue; }
  208.       
  209.       obm[i] = 0;
  210.       deleted++;
  211.     }
  212.       }
  213.     }
  214.     
  215.     fprintf (stderr, "round %3d: %5d deletions\n", round, deleted);
  216.   }
  217.   
  218.   for (obm = output->bm,
  219.         tail = output->bm + output->hdr.plnlen;
  220.        obm < tail; 
  221.        obm++)
  222.   { *obm = *obm ? WHITE : BLACK; }
  223.   
  224.   free_fbm (&temp);
  225.   
  226.   return (1);
  227. }
  228.